package _09_高频题;

/**
 * https://leetcode-cn.com/problems/trapping-rain-water/
 *
 * @Author: haogege
 * @Date: 2021/9/3
 */

public class _42_接雨水 {

    // 时间复杂度O(n)，空间复杂度O (1)
    public int trap(int[] height) {
        if (height == null || height.length == 0) return 0;

        int left = 0, right = height.length - 1, lowMax = 0, water = 0;
        while (left < right) {
            int lower = height[height[left] <= height[right]? left++: right--];
            lowMax = Math.max(lower, lowMax);
            water += lowMax -lower;
        }

        return water;
    }

    // 时间复杂度O(n)，空间复杂度O (n)，左边最小，其实可以在遍历中找到
    public int trap2(int[] height) {
        if (height.length == 0) return 0;

        // 记录每个元素左边，右边对应的最大柱子
        int lastIndex = height.length - 2;
        int[] rightMax = new int[height.length];
        // 右边柱子最大值 O(n)
        for (int i = lastIndex; i >= 1; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i + 1]);
        }

        int water = 0;
        int leftMax = 0;
        for (int i = 1; i <= lastIndex; i++) {
            leftMax = Math.max(leftMax, height[i - 1]);
            int minHeight = Math.min(leftMax, rightMax[i]);
            if (minHeight > height[i]) {
                water += minHeight - height[i];
            }
        }
        return water;
    }

    // 时间复杂度O(n)，空间复杂度O (2n)
    public int trap1(int[] height) {
        if (height.length == 0) return 0;

        // 记录每个元素左边，右边对应的最大柱子
        int lastIndex = height.length - 2;
        int[] leftMax = new int[height.length];
        int[] rightMax = new int[height.length];
        // 左边柱子最大值 O(n)
        for (int i = 1; i <= lastIndex; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i - 1]);
        }
        // 右边柱子最大值 O(n)
        for (int i = lastIndex; i >= 1; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i + 1]);
        }

        int water = 0;

        for (int i = 1; i <= lastIndex; i++) {
            int minHeight = Math.min(leftMax[i], rightMax[i]);
            if (minHeight > height[i]) {
                water += minHeight - height[i];
            }
        }
        return water;
    }

}
